package fr.jgraph.model.graph.old;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

import fr.jgraph.model.edge.Edge;
import fr.jgraph.model.vertex.old.Vertex;

/**
 * A graph is a pair G = {V, E} where V are vertices and E edges. We consider
 * here finite graphs.
 */
public abstract class AbstractGraph {
	/** The name of the graph */
	protected String name;
	
	/** Returns the collection of vertices */
	public abstract Collection getVertices();
	
	/** Returns the collection of edges. */
	public abstract Collection getEdges();
	
	/** Two edges are adjacent iif they have a vertex in common and e1 != e2. */
	public boolean areAdjacent(Edge e1, Edge e2) {
		Vertex[] ends = e1.vertexSet();
		return !e1.equals(e2) && (e2.isIncident(ends[0]) || e2.isIncident(ends[1]));
	}
	
	/** Returns the order of the graph, i.e its number of vertices. */
	public int getOrder() {
		return getVertices().size();
	}

	/** Returns the number of edges, also written ||G||. */
	public int countEdges() {
		return getEdges().size();
	}

	/**
	 * Returns true if the graph is said to be empty, i.e. if its number of
	 * vertices and its number of edges are 0.
	 */
	public boolean isEmpty() {
		return getVertices().isEmpty();
	}

	/** A graph is trivial if its order is 0 or 1. */
	public boolean isTrivial() {
		int order = getOrder();
		return order == 0 || order == 1;
	}
	
	/** Returns true if the graph is complete iif all vertices are pairwise adjacent. */
	public boolean isComplete() {
		Iterator itVertices1 = getVertices().iterator();
		while(itVertices1.hasNext()) {
			Vertex v1 = (Vertex) itVertices1.next();
			Iterator itVertices2 = getVertices().iterator();
			while(itVertices2.hasNext()) {
				Vertex v2 = (Vertex) itVertices2.next();
				if(!v1.equals(v2) && !areAdjacent(v1,v2))
					return false;
			}
		}
		return true;
	}
	
	/**
	 * Returns true if the two vertices are independent if they are pairwise not
	 * adjacent vertices.
	 */
	public boolean areIndependent(Vertex v1, Vertex v2) {
		return !areAdjacent(v1,v2);
	}
	
	/**
	 * Returns true if the two vertices are independent if they are pairwise not
	 * adjacent vertices.
	 */
	public boolean areIndependent(Edge e1, Edge e2) {
		return !areAdjacent(e1,e2);
	}
	
	/** Two vertices are adjacent iif there is an edge linking both of them. */
	public abstract boolean areAdjacent(Vertex v1, Vertex v2);
	
	/**
	 * Returns true if the set of edges is stable, i.e. if no two of its elements
	 * are adjacent.
	 */
	public boolean isEdgeStable(Set set) {
		ArrayList list = new ArrayList(set);
		for (int i = 0; i < list.size(); i++)
			for (int j = 0; j < list.size(); j++)
				if (areAdjacent((Edge) list.get(i), (Edge) list.get(j)))
					return false;
		return true;
	}
	
	/**
	 * Returns true if the set of vertices is stable, i.e. if no two of its elements
	 * are adjacent.
	 */
	public abstract boolean isVertexStable(Set set);
	
	/**
	 * Returns true if this graph is isomorphic to the graph given in parameter.
	 * Two graphs G=(V,E) and G'=(V',E') are isomorphic (written G ~ G') iif there
	 * exists a bijection phi : V -> V' with xy in E <=> phi(x)phi(y) in E' for
	 * all x, y in V. The map phi is called automorphism.
	 */
	public abstract boolean isIsomorphicTo(AbstractGraph graph);
	
	/**
	 * Returns true if the two graphs are automorphic and G=G'.
	 */
	public abstract boolean isAutomorphicTo(AbstractGraph graph);
	
	/** Returns the list of edges where one end is the one given in argument. */
	public Collection getEdges(Vertex vertex) {
		ArrayList edges = new ArrayList();

		Iterator itEdges = getEdges().iterator();
		while (itEdges.hasNext()) {
			Edge edge = (Edge) itEdges.next();
			Vertex[] vertices = edge.vertexSet();
			if (vertices[0].equals(vertex) || vertices[1].equals(vertex))
				edges.add(edge);
		}
		
		return edges;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}
	
	// Partial and subgraphs 
	
	/** G'=(V,E') is a partial graph of G=(V,E) if E' is a subset of E. */
	public boolean isPartialGraphOf(AbstractGraph graph) {
		return equalsVerticesSet(graph)&&isEdgesSubset(graph);
	}
	
	/** Is the edge set a subset of the one of graph ? */
	private boolean isEdgesSubset(AbstractGraph graph) {
		Iterator itEdges = getEdges().iterator();
		while(itEdges.hasNext()) {
			Edge edge = (Edge) itEdges.next();
			if(!graph.getEdges().contains(edge))
				return false;
		}
		
		return true;
	}
	
	/** Is the vertices set a subset of the one of graph ? */
	private boolean isVerticesSubset(AbstractGraph graph) {
		Iterator itVertices = getVertices().iterator();
		while (itVertices.hasNext()) {
			Vertex vertex = (Vertex) itVertices.next();
			if (!graph.getVertices().contains(vertex))
				return false;
		}
		
		return true;
	}
	
	/** Are the two vertices sets equal ? */
	private boolean equalsVerticesSet(AbstractGraph graph) {
		Set set1 = new HashSet(getVertices());
		Set set2 = new HashSet(graph.getVertices());
		if(!set1.equals(set2))
			return false;
		
		return true;
	}
	
	/**
	 * G'=(V',E') is a subgraph of G=(V,E) if V' is a subset of V and E' contains
	 * all the edges of E where the two ends are in V'.
	 */
	public boolean isSubGraphOf(AbstractGraph graph) {
		// Is V' a subset of V ?
		if (!isVerticesSubset(graph))
			return false;

		// Are all edges of E with their two ends in V' contained in E' ?
		Iterator itEdges = graph.getEdges().iterator();
		while (itEdges.hasNext()) {
			Edge edge = (Edge) itEdges.next();
			Vertex[] ends = edge.vertexSet();
			if (getVertices().contains(ends[0]) && getVertices().contains(ends[1])
					&& !getEdges().contains(edge))
				return false;
		}

		return true;
	}
	
	/** A partial subgraph is the partial graph of a subgraph. */
	public boolean isPartialSubGraphOf(AbstractGraph graph) {
		return isEdgesSubset(graph) && isVerticesSubset(graph);
	}
	
	/** A clique is a complete partial subgraph */
	public boolean isCliqueOf(AbstractGraph graph) {
		return isComplete() && isPartialSubGraphOf(graph);
	}
	
	/** A stable (???) is a subgraph with no edge. */
	public boolean isStableOf(AbstractGraph graph) {
		return isSubGraphOf(graph) && getEdges().isEmpty();
	}
	
	// Degrees
	
	/** The degree of a vertex is the number of times it intervenes in edges. */
	public int getDegree(Vertex vertex) {
		int degree = 0;
		Iterator itEdges = getEdges().iterator();
		while(itEdges.hasNext()) {
			Edge edge = (Edge)itEdges.next();
			Vertex[] ends = edge.vertexSet();
			if(ends[0].equals(vertex))
				degree++;
			if(ends[1].equals(vertex))
				degree++;
		}
		return degree;
	}
	
	/** The degree of a graph is the maximal degree of the vertices of the graph */
	public int getDegree() {
		int maxDeg = 0;
		Iterator itVertices = getVertices().iterator();
		while (itVertices.hasNext()) {
			Vertex vertex = (Vertex) itVertices.next();
			int deg = getDegree(vertex);
			if (deg > maxDeg)
				maxDeg = deg;
		}
		return maxDeg;
	}
	
	/** A graph is regular if all its vertices have the same degree. */
	public boolean isRegular() {
		Iterator itVertices = getVertices().iterator();

		if (!itVertices.hasNext())
			return true;

		Vertex vertex = (Vertex) itVertices.next();
		int degree = getDegree(vertex);
		while (itVertices.hasNext()) {
			vertex = (Vertex) itVertices.next();
			if (getDegree(vertex) != degree)
				return false;
		}
		return true;
	}
}	
